package com.zjw.algorithm.ready1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class _全排序 {

    public static void main(String[] args) {
        System.out.println(new _全排序().permute(new int[]{1, 2, 3}));
    }

    public List<List<Integer>> permute(int[] nums) {


        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        doPermute(nums, 0, result);

        return result;
    }

    private void doPermute(int[] arr, int position, List<List<Integer>> result) {
        if (position == arr.length) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i : arr) {
                list.add(i);
            }
            result.add(list);
            return;
        }

        for (int i = position; i < arr.length; i++) {
            int temp = arr[i];
            arr[i] = arr[position];
            arr[position] = temp;


            doPermute(arr, position + 1, result);

            //回溯
            temp = arr[i];
            arr[i] = arr[position];
            arr[position] = temp;
        }

    }

}
